package org.nowcoder.leetcode.backTracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Title  : 40. Combination Sum II
 * Source : https://leetcode.cn/problems/combination-sum-ii/description/
 * Author : XrazYang
 * Date   : 2024-1-31
 */

public class LeetCode_40 {
    private final List<List<Integer>> result = new ArrayList<>();
    private final LinkedList<Integer> path = new LinkedList<>();

    private void backTracking4(int[] candidates, int sum, int target, int start, boolean[] used) {
        if (sum == target) { // 终止条件
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length && (sum + candidates[i] <= target); i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) { //去重
                continue;
            }
            sum += candidates[i];
            path.add(candidates[i]);
            used[i] = true;
            backTracking4(candidates, sum, target, i + 1, used); // 元素重复使用
            sum -= candidates[i];
            used[i] = false;
            path.removeLast();
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        backTracking4(candidates, 0, target, 0, used);
        return result;
    }
}
